package 动态规划;

import java.util.Arrays;

//322 零钱兑换
public class Solution2 {
    class Solution {
        public int coinChange(int[] coins, int amount) {
            int[][] dp = new int[coins.length + 1][amount + 1];
            Arrays.fill(dp[0], 10001);
            dp[0][0] = 0;
            for (int i = 1 ; i <= coins.length ; i++) {
                for (int j = 0 ; j <= amount ; j++) {
                    if (j >= coins[i - 1])
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                    else
                        dp[i][j] = dp[i - 1][j];
                }
            }
            return dp[coins.length][amount] == 10001 ? -1 : dp[coins.length][amount];
        }
    }
}
